Introduction

This is the most natural security definition for public-key encryption schemes, since the public key $k_{e}$ is available for anyone to see. Any realistic adversary would have access to it, and, since they know the encryption algorithm, they can use $k_{e}$ to encrypt any message they like. This is the reason why chosen-plaintext security is the minimal security guarantee which is expected of public-key encryption schemes.

Definition: CPA-Security

The efficient adversary $Eve$ is given the public key $k_{e}$ and can use it to encrypt $q$ messages of her choice $m_{1}, ..., m_{q}$ to obtain their corresponding ciphertexts $c_{1}, ..., c_{q}$ .

A public-key encryption scheme $(Gen, Enc, Dec)$ is CPA-secure if for any two messages $(μ_{0}, μ_{1})$ , public key $k_{e}$ generated by $Gen$ and ciphertext $c : = Enc (k_{e}, \cdot)$ which is the encryption of either $μ_{0}$ or $μ_{1}$ , the probability that Eve can guess whether $c$ belongs to $μ_{0}$ or $μ_{1}$ is at most negligibly greater than $\frac{1}{2}$ .

$k_{e} \leftarrow Gen (), b \leftarrow_{R} {0, 1} Pr [Eve (k_{e}, Enc (k_{e}, μ_{b})) = μ_{b}] \leq \frac{1}{2} + negl ()$

Definition Breakdown

The adversary Eve is not explicitly given access to an encryption oracle because she has the public key, knows the encryption algorithm and can thus encrypt any messages she likes. She is also free to choose the messages $μ_{0}, μ_{1}$ . The public-key encryption scheme is considered CPA-secure if no matter what Eve does, she cannot guess if a ciphertext $c$ is the encryption of $μ_{0}$ or $μ_{1}$ with significantly better probability than $\frac{1}{2}$ .

As with private-key CPA-security, any public-key encryption scheme must use a nondeterministic $Enc$ function.

Necessity of Randomness

There is no CPA-secure public-key encryption scheme with a deterministic encryption function $Enc$ .

If the encryption algorithm $Enc$ were deterministic, then Eve would be able to simply pass $μ_{0}$ and $μ_{1}$ to it and compare $c$ with the resulting ciphertexts. Non-determinism protects against this by producing a different ciphertext every time that the same message is encrypted.

The Cyberclopaedia

Introduction